Solution: Combination Sum

Statement#

Given an array of distinct integers, nums, and an integer, target, return a list of all unique combinations of nums where the chosen numbers sum up to the target. The combinations may be returned in any order.

An integer from nums may be chosen an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen integers is different.

Constraints:

• $1 \leq$ nums.length $\leq 30$
• $2 \leq$ nums[i] $\leq 40$
• $1 \leq$ target $\leq 40$
• All integers of nums are unique.

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

A naive approach to solve this problem would be to make all the possible combinations of nums or generate all subsets of nums that sum up to the required target.

This solution is very costly because the time complexity of achieving this is $O(n^{t/m})$, where $n$ is the number of elements in nums, $t$ is the target, and $m$ is the minimum value in nums. This is because each node in the recursion tree can have $n$ branches, and the height of the tree can grow up to $t/m$. Therefore, the total number of nodes in such a tree is bounded by $n^{t/m}$.

Optimized solution using dynamic programming#

Because the recursive solution to this problem is very costly, let’s see if we can reduce this cost in any way. Dynamic programming helps us avoid recomputing the same subproblems. Now let’s analyze our recursive solution to see if it has the properties needed for conversion to dynamic programming.

• Optimal substructure: Let’s say we want to find the solution to the problem of counting a value, target, given $n$ numbers. Since we know the answer to the $n$ subproblems formed by subtracting each of the $n$ numbers from the target, we can simply sum up the answer to these subproblems. This gives us the answer to our original problem. Therefore, this problem obeys the optimal substructure property.

• Overlapping subproblems: The algorithm solves the same subproblems repeatedly, so it also has the second property of dynamic programming. For example, for nums=[2,3,4] and target=6, we know that $4$ can be generated in two ways, i.e., $2+2$ and $4$. Now, when we try to generate $6$, we know that one way to generate it is using $2$ and $4$. For this, the algorithm will try to generate $4$ again even though we’ve already computed it.

Let’s look at the dynamic programming approach to solving this problem. We first create a table, dp, of size $(t+1)$, where $t$ is the target value. Each cell of our table, dp[i], represents the combination to make the target value $i$ using elements from nums.

First, for target $i=0$, we add “[ ]” in dp[0] because there is only one way to make a target of $0$ by using none of the available options. After this, for any target $i > 0$ and each $j^{th}$ number in nums, we only select this number if nums[j] <= i. After selecting a number nums[j], we traverse all combinations in dp[i-nums[j]] because each combination in that cell represents a combination that can sum up to target i after adding nums[j] to it. For each such combination, we append nums[j] to it, sort it to avoid redundancy, and check whether it already exists in dp[i]. If not, we append this combination to dp[i]. We repeat this process until we’ve processed all target values. Finally, the last cell of the table, dp[target], gives us the unique combinations of nums that make up the target.

Let’s look at the following illustration to get a better understanding of the algorithm:

Solution summary#

To recap, the solution to this problem can be divided into the following parts:

1. Initialize dp to store the results. Each cell of dp stores the combinations that sum up to the $i^{th}$ value, where $i$ ranges from $0$ to target.

2. Add “[ ]” in dp[0] for target $i=0$.

3. For each value $i>0$ and $j^{th}$ number in nums, select this number if nums[j] <= i.

4. Append nums[j] to each previously calculated combination in dp[i-nums[j]], and add it to dp[i] if it doesn’t already exist in it.

5. Finally, return dp[target] that contains all the combinations that sum up to target.

Time complexity#

The time complexity of this solution is $O(t \times n \times s^2log(s))$, where $t$ is the target, $n$ is the length of nums, and $s=t/m$, where $m$ is the minimum value in nums. This is because $O(t)$, $O(n)$, and $O(s)$ time is taken by the first, second, and third loop, respectively. Moreover, $O(slog(s))$ time is taken by the sorting.

Space complexity#

The space complexity of this algorithm is $O(t \times n)$.